package alo.p19;

/**
 * @ClassName MatrixAllOnes
 * @Description 所有元素为1的最大子方阵
 * @Author Fanxc
 * @DATE 2021/3/15 17:21
 * @Version 1.0
 */
public class MatrixAllOnes {
    void matrixAllOnes(int[][] B,int m,int n){
        int[][] L=new int[m][n];
        for (int i = 0; i < m; i++) {
            L[i][0]=B[i][0];
        }
        for (int i = 0; i < n; i++) {
            L[0][i]=B[0][i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(B[i][j]==1){
                    L[i][j]=Math.min(Math.min(L[i][j-1],L[i-1][j]),L[i-1][j-1]+1);
                }else {
                    L[i][j]=0;
                }
            }
        }
        int max_of_s=L[0][0];
        int max_i=0,max_j=0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (L[i][j] > max_of_s) {
                    max_of_s = L[i][j];
                    max_i = i;
                    max_j = j;
                }
            }
        }
        //输出
        for (int i = max_i; i >max_i-max_of_s; i--) {
            for (int j = max_j; j > max_j - max_of_s; j--) {
                System.out.println(B[i][j]);
            }
        }
    }
}
